package com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.algorithms.mst;

import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Edge;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Graph;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Vertex;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.line.PriorityQueue;
import lombok.Setter;
import lombok.experimental.Accessors;

import java.util.*;

/**
 * <h1>Prim延时版本</h1>
 * <h2>过程</h2>
 * <p>
 *     从一个节点开始，递归如下操作：
 *     标记节点，将节点的列放入优先级队列，循环从优先级队列中获取权重最小的边，判断边的两个节点都未被同时标记，将这个边放入结果集，标记节点，并把标记节点的边放入优先队列。
 *     直到边中没有数据或者已经遍历到V-1
 * </p>
 *
 */
public class LasyPrimMST<T> {
    @Setter
    @Accessors(chain = true)
    private Graph<T> graph;
    private List<Edge<T>> mst ;

    private PriorityQueue<Edge<T>> priorityQueue;

    Set<Vertex<T>> mark;

    public Iterable<Edge<T>> mst(){
        return mst;
    }




    private LasyPrimMST<T> init(){

        this.graph.getVertices().entrySet().stream().map(Map.Entry::getValue).findAny().ifPresent(this::visit);

        //队列中没有数据或者已经遍历了V-1条。
        while(priorityQueue.isEmpty()||mst.size()<this.graph.getVertices().entrySet().size()-1){
            Edge<T> min = priorityQueue.pull();
            //都标记了说明不符合规则。
            if(mark.contains(min.getTo())&&mark.contains(min.getFrom())){
                continue;
            }
            this.mst.add(min);
            if (mark.contains(min.getTo())) {
                visit(min.getFrom());
                continue;
            }
            if (mark.contains(min.getFrom())) {
                visit(min.getTo());
                continue;
            }
        }

        return this;
    }

    /**
     * 标记某个顶点，并把顶点中的列放在优先队列中。
     * @param vertex
     */
    private void visit(Vertex<T> vertex){
        mark.add(vertex);
        vertex.getNext().forEach(tEdge -> {
            if(!mark.contains(tEdge.other(vertex))){//过滤掉已经存在的
                priorityQueue.insert(tEdge);
            }
        });


    }


    private LasyPrimMST(Graph<T> graph){
        this.graph = graph;
        this.mst = new ArrayList<>(graph.getVertices().keySet().size() - 1);
        priorityQueue = new PriorityQueue(new Edge<T>().getClass(), graph.getVertices().keySet().size() * 2, true);
        mark = new HashSet<>(graph.getVertices().keySet().size());

    }

    public static <T> LasyPrimMST<T> create(Graph<T> graph){
        return new LasyPrimMST<>(graph).init();
    }

}
